package leetcode.array.sum;

import java.util.Arrays;

/**
 * 167. 两数之和 II - 输入有序数组
 *
 * 解法
 *      1 双指针法
 *          使用双指针从数组的左右两边依次递进 (推荐)
 *      2 二分查找
 *          固定一个数, 第二个数使用二分查找
 *
 */
public class SortTwoSum {

    public static void main(String[] args) {
        SortTwoSum solution = new SortTwoSum();
        int[] nums = {2, 7, 11, 15};
        int target = 9;
        int[] res = solution.twoSum2(nums, target);

        System.out.println(Arrays.toString(res));
    }

    /**
     * 使用二分查找 时间复杂度是 O(nlogn)
     *
     * @param numbers   数组
     * @param target    指定值
     * @return
     */
    public int[] twoSum(int[] numbers, int target) {
        int n = numbers.length;
        for (int i = 0; i < n - 1; i++) {
            int index = binarySearch(numbers, i + 1, target - numbers[i]);
            if (index != -1) {
                return new int[]{i + 1, index + 1};
            }
        }
        return new int[2];
    }


    /**
     * 双指针法 时间复杂度是 O(n)
     *
     * @param numbers 数组
     * @param target  指定值
     * @return
     */
    public int[] twoSum2(int[] numbers, int target) {
        int n = numbers.length;
        int left = 0;
        int right = n - 1;
        while (left <= right) {
            int sum = numbers[left] + numbers[right];
            if (sum < target) {
                left++;
            } else if (sum > target) {
                right--;
            } else {
                return new int[]{left + 1, right + 1};
            }
        }
        return new int[]{-1, -1};
    }


    /**
     * 二分查找
     *
     * @param nums   数组
     * @param left   左指针
     * @param target 指定值
     * @return
     */
    public int binarySearch(int[] nums, int left, int target) {
        int n = nums.length;
        int right = n - 1;
        int mid;
        while (left <= right) {
            mid = (left + right) / 2;
            int midValue = nums[mid];
            if (midValue < target) {
                left = mid + 1;
            } else if (midValue > target) {
                right = mid - 1;
            } else {
                return mid;
            }
        }
        return -1;
    }
}
